package com.hle.map;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import com.hle.map.HashMap.Node;
import com.mj.printer.BinaryTreeInfo;
import com.mj.printer.BinaryTrees;

public class HashMap<K, V> implements Map<K, V> {
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	private static final int DEFAULT_CAPACITY = 1 << 4;
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
	private int size;
	private Node<K, V>[] table;

	public HashMap() {
		table = new Node[DEFAULT_CAPACITY];
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;

	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		size = 0;
		for (int i = 0; i < table.length; i++) {
			table = null;
		}
	}

	@Override
	public V put(K key, V value) {
		resize();
		int index = index(key);
		Node<K, V> root = table[index];
		if (root == null) {
//			root = new Node<>(key, value, null);
			root = createNode(key, value, null);
			table[index] = root;
			size++;
			afterPut(root);
			return null;
		}

		Node<K, V> node = root;
		Node<K, V> parent = null;
		int cmp = 0;
		K k1 = key;
		int h1 = hash(k1);
		Node<K, V> result;
		while (node != null) {
			K k2 = node.key;
			int h2 = node.hash;
			if (h1 > h2) {
				cmp = 1;
			}else if (h1 < h2) {
				cmp = -1;
			}else if (Objects.equals(k1, k2)) {
				cmp = 0;
			}else if ( k1 != null && k2 != null
					&& k1.getClass() == k2.getClass()
					&& k1 instanceof Comparable 
					&& (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
			}else { /// 扫描
				if (node.left != null &&  (result = node(node.left, k1)) != null ||
					node.right != null &&  (result = node(node.right, k1)) != null	) {
					node = result;
					cmp = 0 ;
				}else {
					cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
				}
			}
			
			parent = node;
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			} else {
				V oldValue = node.value;
				node.key = key;
				node.value = value;
				return oldValue;
			}
		}
//		Node<K, V> newNode = new Node<>(key, value, parent);
		Node<K, V> newNode = createNode(key, value, parent);
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		size++;
		afterPut(newNode);
		return null;
	}

	@Override 
	public V get(K key) {
		// TODO Auto-generated method stub
		Node<K, V> node = node(key);
		return node == null ? null : node.value;
	}

	@Override
	public V remove(K key) {
		// TODO Auto-generated method stub
        System.out.println("麻痹的1"+key);
        Node<K, V> node = node(key);
        System.out.println("麻痹的1"+node);
		return remove(node(key));
	}

	@Override
	public boolean containsKey(K key) {
		// TODO Auto-generated method stub
		Node<K, V> node =  node(key);
		return node == null ? false : true;
	}

	@Override
	public boolean containsValue(V value) {
		// TODO Auto-generated method stub
		Queue<Node<K, V>> queue = new LinkedList<>();
		for (int i = 0; i < table.length; i++) {
			Node<K, V> root = table[i];
			if (root == null) continue;
			queue.offer(root);
			while (!queue.isEmpty()) {
				Node<K, V> node = queue.poll();
				if (Objects.equals(node.value, value)) return true;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
		return false;
	}

	@Override
	public void traversal(Visitor<K, V> visitor) {
	if (size == 0 || visitor == null) return;
		
		Queue<Node<K, V>> queue = new LinkedList<>();
		for (int i = 0; i < table.length; i++) {
			if (table[i] == null) continue;
			
			queue.offer(table[i]);
			while (!queue.isEmpty()) {
				Node<K, V> node = queue.poll();
				if (visitor.visit(node.key, node.value)) return;
				
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
	}
	
	protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
		return new Node<>(key, value, parent);
	}

	public void printTree() {
		for (int i = 0; i < table.length; i++) {
			if (size == 0) return;
			System.out.println("===========================");
			System.out.println("【index = " + i + "】");
			Node<K, V> root = table[i];
			BinaryTrees.println(new BinaryTreeInfo() {

				@Override
				public Object string(Object node) {
					// TODO Auto-generated method stub
					return node;
				}

				@Override
				public Object root() {
					// TODO Auto-generated method stub
					return root;
				}

				@Override
				public Object right(Object node) {
					// TODO Auto-generated method stub
					return ((Node<K, V>)node).right;
				}

				@Override
				public Object left(Object node) {
					// TODO Auto-generated method stub
					return ((Node<K, V>)node).left;
				}
			});
		}
	}

	private Node<K, V> node(K key) {
		int index= index(key);
		Node<K, V> node = table[index];
		return node == null ? null : node(node, key);
	}
	
	@SuppressWarnings({ "unchecked", "rawtypes" })
	private Node<K, V> node(Node<K, V> node, K k1) {
		int h1 = hash(k1);
		// 存储查找结果
		Node<K, V> result = null;
		int cmp = 0;
		while (node != null) {
			K k2 = node.key;
			int h2 = node.hash;
			// 先比较哈希值
			if (h1 > h2) {
				node = node.right;
			} else if (h1 < h2) {
				node = node.left;
			} else if (Objects.equals(k1, k2)) {
				return node;
			} else if (k1 != null && k2 != null 
					&& k1 instanceof Comparable
					&& k1.getClass() == k2.getClass()
					&& (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
				node = cmp > 0 ? node.right : node.left;
			} else if (node.right != null && (result = node(node.right, k1)) != null) { 
				return result;
			} else { // 只能往左边找
				node = node.left;
			}
		}
		return null;
	}

	protected V remove(Node<K, V> node) {
        System.out.println("麻痹的2"+node);

        if (node == null) return null;
        
        System.out.println("麻痹的2"+1);

        Node<K, V> willNode = node;
        
        size--;
        
        V oldValue = node.value;
        
        if (node.hasTwoChildren()) { // 度为2的节点
            // 找到后继节点
            Node<K, V> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.key = s.key;
            node.value = s.value;
            node.hash = s.hash;
            // 删除后继节点
            node = s;
        }
        
        // 删除node节点（node的度必然是1或者0）
        Node<K, V> replacement = node.left != null ? node.left : node.right;
        int index = index(node.key);
        
        if (replacement != null) { // node是度为1的节点
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                table[index] = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }
            
            // 删除节点之后的处理
            fixAfterRemove(replacement);
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            table[index] = null;
        } else { // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
            
            // 删除节点之后的处理
            fixAfterRemove(node);
        }
        
        // 交给子类去处理
        afterRemove(willNode, node);
        
        System.out.println("麻痹的"+oldValue);
        return oldValue;
    }

	private Node<K,V> successor(Node<K,V> node) {
		if (node == null) {
			return null;
		}
		Node<K,V> p = node.left;
		if (p != null) {
			while (p.right != null) {
				p= p.right;
			}
			return p;
		}

		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}

		return node.parent;
	}

	private int index(K key) {
		if (key == null) return 0;
		int h = key.hashCode();
		return (h ^ (h >>> 16)) & (table.length - 1);
	}
	
	private void resize() {
		if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
		Node<K, V> [] oldTable = table;
		table = new Node[oldTable.length << 1];
		System.out.println("扩容前长度：" + oldTable.length + "扩容后长度：" + table.length);

		Queue<Node<K, V>> queue = new LinkedList<>();
		for (int i = 0; i < oldTable.length; i++) {
			Node<K, V> rootNode = oldTable[i];
			if (rootNode == null) continue;
			queue.offer(rootNode);
			while (!queue.isEmpty()) {
			    Node<K, V> node = queue.poll();
			    if (node.left != null) {
					queue.offer(node.left);
				}
			    if (node.right != null) {
					queue.offer(node.right);
				}
			    moveNode(node);
			}
		}
	}
	
	private void moveNode(Node<K, V> newNode) {
		// 重置
		newNode.parent = null;
		newNode.left = null;
		newNode.right = null;
		newNode.color = RED;
		
		int index = index(newNode.key);
		// 取出index位置的红黑树根节点
		Node<K, V> root = table[index];
		if (root == null) {
			root = newNode;
			table[index] = root;
			afterPut(root);
			return;
		}
		
		// 添加新的节点到红黑树上面
		Node<K, V> parent = root;
		Node<K, V> node = root;
		int cmp = 0;
		K k1 = newNode.key;
		int h1 = newNode.hash;
		do {
			parent = node;
			K k2 = node.key;
			int h2 = node.hash;
			if (h1 > h2) {
				cmp = 1;
			} else if (h1 < h2) {
				cmp = -1;
			} else if (k1 != null && k2 != null 
					&& k1 instanceof Comparable
					&& k1.getClass() == k2.getClass()
					&& (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
			} else {
				cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
			}
			
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			}
		} while (node != null);

		// 看看插入到父节点的哪个位置
		newNode.parent = parent;
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		
		// 新添加节点之后的处理
		afterPut(newNode);
	}
	

	private void afterPut(Node<K, V> node) {
		Node<K, V> parent = node.parent;
		if (parent == null) {
			color(node, BLACK);
			return;
		}

		if (isBlack(parent)) {
			return;
		}

		Node<K, V> uncle = parent.sibling();
		Node<K, V> grand = parent.parent;

		if (isRed(uncle)) {
			black(parent);
			black(uncle);
			red(grand);
			afterPut(grand);
			return;
		} else {
			if (parent.isLeftChild()) { // L
				if (node.isLeftChild()) { // LL
					black(parent);
					red(grand);
					rotateRight(grand);
				} else { // LR
					black(node);
					red(grand);
					rotateLeft(parent);
					rotateRight(grand);
				}
			} else { // R
				if (node.isLeftChild()) { // RL
					black(node);
					red(grand);
					rotateRight(parent);
					rotateLeft(grand);
				} else { // RR
					black(parent);
					red(grand);
					rotateLeft(grand);
				}
			}
		}
	}

	public void afterRemove(Node<K, V> node, Node<K, V> replacement) {
		// TODO Auto-generated method stub
		if (isRed(node))
			return;

		if (isRed(replacement)) {
			black(replacement);
			return;
		}
		Node<K, V> parent = node.parent;
		if (parent == null)
			return;

		/// 删除的是黑色叶子节点
		boolean left = parent.left == null || node.isLeftChild();
		Node<K, V> sibling = left ? parent.right : parent.left;

		if (left) {
			if (isRed(sibling)) {
				black(sibling);
				red(parent);
				rotateLeft(parent);
				sibling = parent.right;
			}

			/// 兄弟节点是黑色
			if (isBlack(sibling.left) && isBlack(sibling.right)) {
				Boolean parentBlack = isBlack(parent);
				red(sibling);
				black(parent);
				if (parentBlack) {
					afterRemove(parent, null);
				}
			} else {
				if (isBlack(sibling.left) && isRed(sibling.right)) { // 黑兄弟左边没有节点
					rotateRight(sibling);
					sibling = parent.right;
				}
				color(sibling, colorOf(parent));
				black(parent);
				black(sibling.right);
				rotateLeft(parent);
			}
		} else {
			if (isRed(sibling)) {
				black(sibling);
				red(parent);
				rotateRight(parent);
				sibling = parent.left;
			}

			/// 兄弟节点是黑色
			if (isBlack(sibling.left) && isBlack(sibling.right)) {
				Boolean parentBlack = isBlack(parent);
				red(sibling);
				black(parent);
				if (parentBlack) {
					afterRemove(parent, null);
				}
			} else {
				if (isBlack(sibling.left) && isRed(sibling.right)) { // 黑兄弟左边没有节点
					rotateLeft(sibling);
					sibling = parent.left;
				}
				color(sibling, colorOf(parent));
				black(parent);
				black(sibling.left);
				rotateRight(parent);
			}

		}

	}

	private boolean isBlack(Node<K, V> node) {
		return colorOf(node) == BLACK;
	}

	private boolean isRed(Node<K, V> node) {
		return colorOf(node) == RED;
	}

	private boolean colorOf(Node<K, V> node) {
		return node == null ? BLACK : node.color;
	}

	private Node<K, V> color(Node<K, V> node, boolean color) {
		if (node != null)
			node.color = color;
		return node;
	}

	private Node<K, V> black(Node<K, V> node) {
		return color(node, BLACK);
	}

	private Node<K, V> red(Node<K, V> node) {
		return color(node, RED);
	}
	
	private void fixAfterRemove(Node<K, V> node) {
		// 如果删除的节点是红色
		// 或者 用以取代删除节点的子节点是红色
		if (isRed(node)) {
			black(node);
			return;
		}
		
		Node<K, V> parent = node.parent;
		if (parent == null) return;
		
		// 删除的是黑色叶子节点【下溢】
		// 判断被删除的node是左还是右
		boolean left = parent.left == null || node.isLeftChild();
		Node<K, V> sibling = left ? parent.right : parent.left;
		if (left) { // 被删除的节点在左边，兄弟节点在右边
			if (isRed(sibling)) { // 兄弟节点是红色
				black(sibling);
				red(parent);
				rotateLeft(parent);
				// 更换兄弟
				sibling = parent.right;
			}
			
			// 兄弟节点必然是黑色
			if (isBlack(sibling.left) && isBlack(sibling.right)) {
				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
				boolean parentBlack = isBlack(parent);
				black(parent);
				red(sibling);
				if (parentBlack) {
					fixAfterRemove(parent);
				}
			} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
				// 兄弟节点的左边是黑色，兄弟要先旋转
				if (isBlack(sibling.right)) {
					rotateRight(sibling);
					sibling = parent.right;
				}
				
				color(sibling, colorOf(parent));
				black(sibling.right);
				black(parent);
				rotateLeft(parent);
			}
		} else { // 被删除的节点在右边，兄弟节点在左边
			if (isRed(sibling)) { // 兄弟节点是红色
				black(sibling);
				red(parent);
				rotateRight(parent);
				// 更换兄弟
				sibling = parent.left;
			}
			
			// 兄弟节点必然是黑色
			if (isBlack(sibling.left) && isBlack(sibling.right)) {
				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
				boolean parentBlack = isBlack(parent);
				black(parent);
				red(sibling);
				if (parentBlack) {
					fixAfterRemove(parent);
				}
			} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
				// 兄弟节点的左边是黑色，兄弟要先旋转
				if (isBlack(sibling.left)) {
					rotateLeft(sibling);
					sibling = parent.left;
				}
				
				color(sibling, colorOf(parent));
				black(sibling.left);
				black(parent);
				rotateRight(parent);
			}
		}
	}


	public void rotateLeft(Node<K, V> node) {
		Node<K, V> parent = node.right;
		Node<K, V> child = parent.left;
		node.right = child;
		parent.left = node;
		afterRotate(node, parent, null);
	}

	public void rotateRight(Node<K, V> node) {
		Node<K, V> parent = node.left;
		Node<K, V> child = parent.right;
		node.left = child;
		parent.right = node;
		afterRotate(node, parent, null);
	}

	public void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
		// 让parent称为子树的根节点
		parent.parent = grand.parent;
		if (grand.isLeftChild()) {
			grand.parent.left = parent;
		} else if (grand.isRightChild()) {
			grand.parent.right = parent;
		} else { // grand是root节点
			table[index(parent.key)] = parent;
		}

		// 更新child的parent
		if (child != null) {
			child.parent = grand;
		}

		// 更新grand的parent
		grand.parent = parent;
	}

	@SuppressWarnings("unchecked")
	private int compare(K k1, K k2, int h1, int h2) {
		/// 比较hash值
		int result = h1 - h2;
		if (result != 0) return result;

		/// 比较euqals
		if (Objects.equals(k1, k2)) return 0;

		/// hash相同，两个类不相等

		if (k1 != null && k2 != null) {
			String k1Cls = k1.getClass().getName();
			String k2Cls = k2.getClass().getName();
			result = k1Cls.compareTo(k2Cls);
			if (result != 0) return result;
			/// 同一种类型
			if (k1 instanceof Comparable) {
				return ((Comparable)k1).compareTo(((Comparable)k2));
			}			
		}	
		return System.identityHashCode(k1) - System.identityHashCode(k2);
	}
	
	private int hash(K key) {
		int hashCode = key == null ? 0 : key.hashCode();
		return hashCode ^ (hashCode >>> 16);
	}

	protected static class Node<K, V> {
		K key;
		V value;
		int hash;
		boolean color = RED;
		Node<K, V> left;
		Node<K, V> right;
		Node<K, V> parent;

		public Node(K key, V value, Node<K, V> parent) {
			this.key = key;
			this.value = value;
			this.parent = parent;
			int hashCode = key == null ? 0 : key.hashCode();
			this.hash  = hashCode ^ (hashCode >>> 16);
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public boolean hasTwoChildren() {
			return left != null && right != null;
		}

		public boolean isLeftChild() {
			return parent != null && this == parent.left;
		}

		public boolean isRightChild() {
			return parent != null && this == parent.right;
		}

		public Node<K, V> sibling() {
			if (isLeftChild()) {
				return parent.right;
			}

			if (isRightChild()) {
				return parent.left;
			}

			return null;
		}
		
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "k:" + key + "_" + "v:" + value;
//			return "k:" + key + ;

		}
	}

}
